package com.atguigui.leetcode;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Java：最小体力消耗路径
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by  wangjiaxin  on 2021/1/29 3:27 下午
 */
/*
你准备参加一场远足活动。给你一个二维rows x columns的地图heights，其中heights[row][col]表示格子(row, col)的高度。一开始你在最左上角的格子(0, 0)，
且你希望去最右下角的格子(rows-1, columns-1)（注意下标从 0 开始编号）。你每次可以往 上，下，左，右四个方向之一移动，你想要找到耗费 体力 最小的一条路径。
一条路径耗费的 体力值是路径上相邻格子之间 高度差绝对值的 最大值决定的。
请你返回从左上角走到右下角的最小体力消耗值。

 求解最短路径的 \texttt{Dijkstra}Dijkstra 算法
 */
public class P1631PathWithMinimumEffort {
    public static void main(String[] args) {
        Solution solution = new P1631PathWithMinimumEffort().new Solution();

    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        //四个方向
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        public int minimumEffortPath(int[][] heights) {
            int m = heights.length;
            int n = heights[0].length;
            PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
                public int compare(int[] edge1, int[] edge2) {
                    return edge1[2] - edge2[2];
                }
            });
            pq.offer(new int[]{0, 0, 0});

            int[] dist = new int[m * n];
            // 将指定的int值赋给指定int数组的每个元素
            Arrays.fill(dist, Integer.MAX_VALUE);
            dist[0] = 0;

            //存放节点
            boolean[] seen = new boolean[m * n];
            //循环便利放入点所有点
            while (!pq.isEmpty()) {
                int[] edge = pq.poll();
                //0 0 0
                int x = edge[0], y = edge[1], d = edge[2];
                //节点编号
                int id = x * n + y;
                if (seen[id]) {
                    continue;
                }
                //到达右下角
                if (x == m - 1 && y == n - 1) {
                    break;
                }
                seen[id] = true;
                //计算上、下、左、右四个方向
                for (int i = 0; i < 4; ++i) {
                    int nx = x + dirs[i][0];
                    int ny = y + dirs[i][1];
                    //判断是否出边界
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && Math.max(d, Math.abs(heights[x][y] - heights[nx][ny])) < dist[nx * n + ny]) {
                        //绝对值比较
                        dist[nx * n + ny] = Math.max(d, Math.abs(heights[x][y] - heights[nx][ny]));
                        //更新最新地点
                        pq.offer(new int[]{nx, ny, dist[nx * n + ny]});
                    }
                }
            }
            //输出最后点
            return dist[m * n - 1];
        }
    }
}
